package demogo

import (
	"container/list"
	"log"
)

type Graph struct {
	adj []*list.List // 邻接表
	v   int          // 顶点个数
}

func NewGraph(v int) *Graph {
	adj := make([]*list.List, v, v)
	for i := 0; i < v; i++ {
		adj[i] = list.New()
	}
	return &Graph{
		adj: adj,
		v:   v,
	}
}

func (g *Graph) AddEdge(s, t int) {
	g.adj[s].PushBack(t)
	//g.adj[t].PushBack(s)
}

// 广度优先搜索

func (g *Graph) BFS(s, t int) []int {
	if s == t {
		return []int{}
	}
	var path = make([]int, 0)
	var prev = make([]int, g.v)
	for i := 0; i < g.v; i++ {
		prev[i] = -1
	}
	var queue = make([]int, 0)

	var visited = make(map[int]bool)
	queue = append(queue, s)
	visited[s] = true
	var isFind = false
	for len(queue) != 0 && !isFind {
		cur := queue[0]
		queue = queue[1:]
		if cur == t {
			isFind = true
			break
		}
		linked := g.adj[cur]
		if linked == nil {
			break
		}
		for e := g.adj[cur].Front(); e != nil; e = e.Next() {
			next := e.Value.(int)
			if visited[next] == false {
				queue = append(queue, next)
				visited[next] = true
				prev[next] = cur
				if next == t {
					isFind = true
					break
				}
			}
		}
	}
	if isFind {
		log.Println("prev ==", prev)
		path = *g.getPathByPrev(prev, s, t, &path)
	}

	return path
}

func (graph *Graph) getPathByPrev(prev []int, s, t int, paths *[]int) *[]int {
	// s和t是同一个节点，以为着到达目的地
	// t起始顶点
	if prev[t] == -1 || t == s {
		*paths = append(*paths, t)
	} else {
		// 假设记录的路径prev是：a <- b <- c <- d
		// 那么从d回到a的路径等价于从c回到a再加上d ===递归的思路
		graph.getPathByPrev(prev, s, prev[t], paths)
		*paths = append(*paths, t)
	}
	return paths
}
